1  Introduction and Overview

In this module, we continue the study of groups that we started in second-year Abstract Algebra. We will, as then, concentrate on finite groups. Following a short introduction and reminder of the essential concepts from Abstract Algebra, we will begin by revisiting permutation groups and use these to introduce the concept of a conjugate. Next we study what happens when groups act on sets, and follow this with a study of the concepts of normal subgroups and quotient groups. Further exploration of group homomorphisms will bring us to one of the major structural theorems for groups, namely the Isomorphism Theorems, which we will be in a position to prove. Finally, we study the three Sylow theorems, proving the first and considering applications of the second and third.

1.1 Basic ideas

In the second year Abstract Algebra module we gave the formal definition of a group:

Definition 1.1 (Groups) A group is a pair \((G, *)\), where \(G\) is a non-empty set and \(*\) is a binary operation defined on \(G\) such that:

1. \(G\) is closed under \(*\), that is \[\forall \, x, y \in G, \; x*y \in G;\]

2. \(*\) is associative on \(G\), that is \[\forall \, x, y, z \in G, \; x * (y * z) = (x * y) * z;\]

3. \(G\) has an identity with respect to \(*\), denoted \(e\), that is \[\exists \, e \in G \; \mbox{such that} \; \forall \, x \in G \\ e * x = x * e = x;\]

4. every \(x \in G\) has an inverse in \(G\), denoted \(x^{-1}\), that is \[\forall \, x \in G \; \exists \, x^{-1} \in G \; \mbox{such that} \\ x * x^{-1} = x^{-1} * x = e.\]

A group with the additional property that \[\forall x, y \in G, x * y = y * x\] is called abelian. You were given lots of examples of structures which satisfy the group axioms. Some of these were infinite and abelian (for example \((\Z, +)\), \((\R, +)\), \((\R \backslash \{0\}, \times)\), and \((\C \backslash \{0\}, \times)\)), some were infinite and non-abelian (for example, \(GL(n, \R)\) under matrix multiplication), some were finite and abelian (for example, \(\Z_n\) and \(\Z^{\times}_m\)), and some were finite and non-abelian (for example, \(D_n\), the group of symmetries of a regular \(n\)-gon).

Initially, we would write groups in the form \((G, *)\) to emphasise the fact that a group is a pair, namely a set of objects and a binary operation defined on that set. In this module we shall, largely, relax that formality and refer to groups simply by the name of the set where there is no ambiguity with regard to the binary operation.

Definition 1.2 (Subgroup) Let \(\gx\) be a group, \(H \subseteq G\) (i.e. \(H\) is a subset of the elements of \(G\)). Then \(H\) is a subgroup of \(G\) if and only if \(\hx\) is a group.

In this module we shall use the notation \(H \leq G\) to denote that \(H\) is a subgroup of \(G\).

To check whether a subset of group elements forms a subgroup we need, in the case of infinite groups, to check that the subset is closed under the group binary operation and that every element of \(H\) has an inverse in \(H\). For finite groups we need only check closure.

Lagrange’s Theorem states that the order of any subgroup must divide the order of the group. The converse is not true for groups in general, but is true for abelian groups.

Recall that for any group element, the set formed by taking all integer powers of that element forms a subgroup. Notationally, if \(\gx\) is a group and \(a \in G\), then the set \(\{ a^n \where n \in \Z \}\) forms a subgroup of \(\gx\) called the cyclic subgroup generated by \(a\) and denoted \(\langle a \rangle\).

Definition 1.3 (Cyclic generator) A group, \(G\), is called cyclic if and only if there exists an element \(a \in G\), called a generator of \(G\), such that \(G = \langle a \rangle\).

Example 1.1  

The group \((\Z, +)\) is cyclic and \(1\) is a generator.

The group \((\R, +)\) is not cyclic.

The subgroup \(\{e, s_1\}\) of \(D_n\) for any \(n\) is cyclic and generated by \(s_1\).

Note that if \(\gx\) is a cyclic group with generator \(a\), then the order of \(G\) is the same as the period of \(a\) in \(G\). In addition, note that the order of a cyclic subgroup generated by \(a \in G\) is the same as the period of \(a\) in \(G\). For this reason we shall not refer to the period of an element in a group, but, more naturally, to its order (though they mean the same thing). Recall, also, that if \(\gx\) is a finite group of prime order, then it must be cyclic.

Definition 1.4 (Order of an element) Let \(\gx\) be a group with identity element \(e\) and consider \(a \in G\). If, for all positive integers \(n\), \(a^n \neq e\), then \(a\) has infinite order. Otherwise, the order of \(a\) is the smallest positive integer \(k\) such that \(a^k = e\).

Example 1.2  

In \(D_4\), \(r_1\) has order \(4\) since \[r_1 \circ r_1 \circ r_1 \circ r_1 = r_1^{4} = e.\]

In \((\Z, +)\), \(1\) has infinite order.

An important consequence of Lagrange’s theorem is that the order of any element in a group must divide the order of the group.

You were then told that any finite group could be completely described by its operation, or Cayley, table.

\(\begin{array}{ccccc} \begin{array}{c|c} &0\\ \hline 0&0 \end{array} & \hspace{1cm} \begin{array}{c|cc} &0&1\\ \hline 0&0&1\\ 1&1&0 \end{array} & \hspace{1cm} \begin{array}{c|ccc} &0&1&2\\ \hline 0&0&1&2\\ 1&1&2&0\\ 2&2&0&1 \end{array} & \hspace{1cm} \begin{array}{c|cccc} &0&1&2&3\\ \hline 0&0&1&2&3\\ 1&1&2&3&0\\ 2&2&3&0&1\\ 3&3&0&1&2 \end{array} & \hspace{1cm} \begin{array}{c|cccc} &0&1&2&3\\ \hline 0&0&1&2&3\\ 1&1&0&3&2\\ 2&2&3&0&1\\ 3&3&2&1&0 \end{array}\\\\ {\Z}_1&\hspace{1cm} {\Z}_2&\hspace{1cm} {\Z}_3&\hspace{1cm}\Z_4&\hspace{1cm}\Z_2\times\Z_2 \end{array}\)

\(\begin{array}{ccc} \begin{array}{c|ccccc} &0&1&2&3&4\\ \hline 0&0&1&2&3&4\\ 1&1&2&3&4&0\\ 2&2&3&4&0&1\\ 3&3&4&0&1&2\\ 4&4&0&1&2&3 \end{array} & \hspace{1cm} \begin{array}{c|cccccc} &0&1&2&3&4&5\\ \hline 0&0&1&2&3&4&5\\ 1&1&2&3&4&5&0\\ 2&2&3&4&5&0&1\\ 3&3&4&5&0&1&2\\ 4&4&5&0&1&2&3\\ 5&5&0&1&2&3&4 \end{array} & \hspace{1cm} \begin{array}{c|cccccc} &0&1&2&3&4&5\\ \hline 0&0&1&2&3&4&5\\ 1&1&2&0&5&3&4\\ 2&2&0&1&4&5&3\\ 3&3&4&5&0&1&2\\ 4&4&5&3&2&0&1\\ 5&5&3&4&1&2&0 \end{array}\\\\ \Z_5&\hspace{1cm}{\Z}_6&\hspace{1cm}S_3\cong D_3 \end{array}\)

Here we have chosen to use the set \(\{0, 1, \ldots , n-1 \}\) to denote the group elements. This is a natural choice when representing the cyclic group of order \(n\) because the Cayley table corresponds to the operation table for addition modulo \(n\), but for the non-cyclic groups, \(\Z_2 \times \Z_2\) and \(S_3\), no particular meaning should be ascribed to these symbols. Indeed, we may take any of these groups and replace the symbols with \(a, b, c, \ldots\) or Cat, Dog, Goldfish, … to obtain a group which, although formally different to the original group (because the underlying set is different) is ‘essentially the same’. This concept of two structures being ‘essentially the same’ is called isomorphism.

Definition 1.5 (Isomorphism) Let \((G_1, *)\) and \((G_2, \odot)\) be groups. Then \((G_1, *)\) and \((G_2, \odot)\) are isomorphic if and only if there exists a mapping \(\theta : G_1 \rightarrow G_2\) (called an isomorphism) such that

1. \(\theta\) is bijective, and
2. \(\forall \, x, y \in G_1\), \(\theta (x*y) = \theta (x) \odot \theta (y)\).

An important skill in pure mathematics is to see through the formalism of statements and definitions and understand what is being said. If you do this then concepts will become natural (maybe even obvious) and you will not need to remember very much. Isomorphism is a case in point. If we want to capture the idea that the elements of the Cayley table of one group can be relabelled so as to obtain the Cayley table of another group (subject to some possible rearrangement of the rows and/or columns), then we need to replace each symbol of the first group with a symbol from the second group. This relabelling is exactly what a bijection achieves (make sure you understand why it needs to be both injective and surjective) and, if the resulting Cayley tables are going to be the same, we require the additional property that

\[\begin{array}{c|ccc} *&&y&\\ \hline &&\vdots&\\ x&\cdots&z&\\ &&& \end{array} \hspace{1cm} \longmapsto \hspace{1cm} \begin{array}{c|ccc} \odot&&\theta(y)&\\ \hline &&\vdots&\\ \theta(x)&\cdots&\theta(z)&\\ &&& \end{array}\]

Or, in other words, \(\theta (x*y) = \theta (x) \odot \theta (y)\). Note that if \(\theta\) is an isomorphism from \(G_1\) to \(G_2\) then \(\theta^{-1}\) is an isomorphism from \(G_2\) to \(G_1\), so we say that \(G_1\) and \(G_2\) are isomorphic and write \(G_1 \cong G_2\). It is important to understand the relationship between cyclic and abelian; if a group is cyclic then it is abelian, but the converse does not necessarily hold. Consider \(\Z^{\times}_{12}\), which has the following operation table:

\[\begin{array}{c|cccc} \otimes_{12}&1&5&7&11\\ \hline 1&1&5&7&11\\ 5&5&1&11&7\\ 7&7&11&1&5\\ 11&11&7&5&1 \end{array}\] Clearly the group is abelian (since the operation involves only the multiplication of integers), but note that all non-identity elements have period 2, so the group cannot be cyclic (since the generator of a cyclic group must have period equal to the order of the group).

If in Definition 1.5, we remove condition a. then the resulting map \(\theta\) is what is called a homomorphism. In particular, homomorphisms preserve the ‘multiplicative structure’ but not necessarily the size. More formally, we have:

Definition 1.6 (Homomorphism) Let \((G_1, *)\) and \((G_2, \odot)\) be groups. Then a map \(\theta : G_1 \rightarrow G_2\) such that \[\forall \, x, y \in G_1, \ \theta (x*y) = \theta (x) \odot \theta (y)\] is called a homomorphism.

Note

An isomorphism is a bijective homomorphism.

Definition 1.7 (Left Coset) Let \(\hx\) be a subgroup of \(\gx\). For a fixed element \(g \in G\), the set \(gH = \{gh \where h \in H\}\) is a left coset of \(H\) in \(\gx\). If \(H = \{h_1, h_2, \ldots, h_m\}\) is finite, then \(gH = \{g \times h_1, g \times h_2, \ldots, g \times h_m\}\).

Left (or right) cosets are an extremely important concept in this module; in fact, much of the material from Chapter 4 onwards is centred around the idea of groups where the elements of the set are themselves cosets (the so-called quotient groups).

1.2 Equivalence Relations

In first-year Algebra, and Abstract Algebra last year, we used the concept of integers being congruent, or equivalent, to each other modulo some given integer. Formally we have the following:

Definition 1.8 (Congruence of Integers) Let \(a, b, n\) be integers, \(n > 0\). Then \(a\) is congruent to \(b\) modulo \(n\) if and only if \(n \divides (b-a)\).

Notationally, we write that \(a \equiv b \modu n)\). Recall, also, that if two integers are equivalent to each other modulo \(n\), that is the same as saying that they both leave the same principal remainder on division by \(n\). In Abstract Algebra we took this one step further and defined a residue class as follows:

Definition 1.9 (Residue Class) Let \(a, n\) be integers, \(n\) positive. The residue class \([a]_n\) of \(a\) modulo \(n\) is the set of all integers congruent to \(a\) modulo \(n\). (Or, the equivalence class containing \(a\) under congruence modulo \(n\).). That is, \[[a]_n = \{m \where m \in \Z, m \equiv a \modu n) \} = \{a+kn \where k \in \Z \}.\]

Example 1.3  

\[\begin{align*} [5]_6 &= \{5+6k | k \in \Z\} = \{\ldots, -7, -1,5,11,17, \ldots \}\\ [0]_5 &= \{5k | k \in \Z\} = \{ \ldots, -10,-5,0,5,10,\ldots\} \end{align*}\]

We note two things about these residue classes. First, for any integers \(a, b, c\), then \(a\) is in the same class as itself; if \(a\) is in the same class as \(b\) then \(b\) is in the same class as \(a\); if \(a\) is in the same class as \(b\) and \(b\) in the same class as \(c\) then \(a\) is in the same class as \(c\). Second, for any given \(n\), the classes partition the set of integers into disjoint sets where every integer is in exactly one of the residue (or equivalence) classes.

Example 1.4  

Consider \([3]_4\) \[ [3]_{4} = \{3+ 4k | k \in \Z \} = \{ \ldots, -9,-5,-1,3,7,11,15,\ldots\} \]

It is clear that \(7\) is contained in its equivalence class. The following are also straightforward

• as \(3\) is in the same equivalence class as \(19\), then \(19\) is in the same equivalence class as \(3\);
• As \(-5\) is in the same equivalence class as \(7\), and \(7\) is in the same equivalence class as \(11\), then \(-5\) is in the same equivalence class as \(11\).

The second property is illustrated below:

\[\begin{align*} [0]_3 &= \{\ldots, -6, -3, 0, 3, 6, 9, \ldots \} \\ [1]_3 &= \{\ldots, -5, -2, 1, 4, 7, 10, \ldots \} \\ [2]_3 &= \{\ldots, -4, -1, 2,5, 8,11 \ldots \} \end{align*}\]

So ‘equivalence modulo’ \(3\) partitions the integers into three disjoint sets — every integer is in one and only one of the 3 sets.

We can formalise these two ideas as follows.

Definition 1.10 (Relation) A relation, \(R\), on a non-empty set \(S\) is a non-empty subset of the Cartesian product \(S \times S\).

Note that, as a consequence of this definition, \(R\) is a set of ordered pairs of elements from \(S\), but rather than specifying a subset \(R\) of \(S \times S\), it is usual to specify a rule for when \((a, b) \in R\), where \(a, b \in S\). We write \(aRb\) rather than \((a, b) \in R\) and read this as \(a\) is related to \(b\) (under the relation \(R\)).

Example 1.5 The following are examples of relations.

1. Let \(S = \{1, 2, 3, 4, 5, 6, 7\}\) and define a relation on \(S\) such that for all \(a, b \in S, \; aRb \ifif \frac{a-b}{2} \in \Z\).

   So \(1R1\) as \((1-1)/2 = 0 \in \Z\); \(2R6\) as \((2-6)/2 = -2 \in \Z\). However, \(3 {R \mkern -11mu/} 4\) since \((3-4)/2 = -1/2 \notin \Z\).

2. Define the relation \(R = \{ (x, y) \where x \in \Z^+, y \in \Z^+, x \neq y \; \text{and} \; x^y = y^x \}\). What does \(R\) contain?

   In fact \(R\) is finite and has only \(2\) elements: \[R = \{(2,4),(4,2)\}.\]

Definition 1.11 (Equivalence Relation) A relation, \(R\), on a non-empty set \(S\) is said to be an equivalence relation if and only if, for all \(a, b, c \in S\),

1. \(aRa\) for all \(a \in S\) (the relation is reflexive) and
2. whenever \(aRb\), then \(bRa\) (the relation is symmetric) and
3. whenever \(aRb\) and \(bRc\), then \(aRc\) (the relation is transitive).

Definition 1.12 (Partition) A partition of a set, \(S\), is a collection, \(P\), of non-empty subsets of \(S\) such that every element of \(S\) is in exactly one member of \(P\).

Note that each member of \(P\) is, in itself, a set.

Theorem 1.1 Let \(R\) be an equivalence relation defined on a set \(S\) and define \[[a] = \{b \in S \where bRa \}.\] Then, \(\{ [a] \where a \in S \}\) is a partition of \(S\).

Proof.

We need to show that every element of \(S\) belongs to one of these sets and also that any two such sets which have an element in common must in fact be equal.

Let \(a \in S\) be arbitrary. Since \(R\) is an equivalence relation, it is reflexive and so \(aRa\) holds. Therefore, by definition, \(a \in [a]\). Since \(a\) was arbitrarily chosen, we conclude that for all \(a \in S\) \(a \in [a]\).

Now let \(a,b \in S\) and suppose that \([a]\) and \([b]\) have a point \(c\) in common, that is \[ c \in [a] \cap [b].\] Let \(a' \in [a]\) be chosen arbitrarily. Since \(a'\) and \(c'\) are in \([a]\) it follows that \(a' R a\) and \(c Ra\). Since \(R\) is a symmetric relation we deduce that \(a R c\) is true as well. Since \(R\) is transitive, the statements \(a' Ra\) and \(aRc\) now mean that \(a' R c\). Using the fact that \(c \in [b]\) we have \(c Rb\). Applying symmetry again we deduce that \(b Rc\) is true also. Transitivity, from the statements \(a' R c\) and \(c R b\), now implies that \(a' R b\). By definition it follows that \(a' \in [b]\). Since \(a' \in [a]\) was arbitrarily chosen we conclude that \([a] \subseteq [b]\).

Swapping the roles of \([a]\) and \([b]\) above, we see that \([b] \subseteq [a]\) as well. Therefore \([a] = [b]\) as required.

We will often refer to each of the members of a partition as an equivalence class. Note that, as a consequence of the above, residue classes are defined by an equivalence relation on the set of integers and, therefore, partition the set of integers. We now return to the property of isomorphism. It is obvious that any group is isomorphic to itself. Furthermore, if \(\theta\) is an isomorphism from \(G_1\) to \(G_2\) then we have noted that \(\theta^{-1}\) is an isomorphism from \(G_2\) to \(G_1\); so if \(G_1 \cong G_2\) then \(G_2 \cong G_1\). An extension of this argument then leads us to the conclusion that if \(G_1 \cong G_2\) and \(G_2 \cong G_3\), then \(G_1 \cong G_3\). Thus isomorphism is an equivalence relation on the collection of all groups (the collection of all groups is technically not a proper set). Now let us consider left coset formation. You will recall that we used a direct argument in Abstract Algebra to show that left cosets partition the group elements (and, along with two other properties we used this to prove Lagrange’s Theorem). This means, therefore, that left coset formation must be an equivalence relation on the set of group elements and if we can define such an equivalence relation we would have an alternative proof to Lagrange’s Theorem. So, let \(G\) be a finite group and \(H\) be a subgroup of \(G\). Consider \(a, b \in G\). We need to find a relation that describes the property of \(a\) and \(b\) lying in the same left coset of \(H\) as each other, that is, \(a\) is related to \(b\) if and only if both \(a\) and \(b\) are in the same left coset of \(H\) in \(G\). Now, since for any subgroup \(H\) we have that \(e \in H\), it follows that \(a\) and \(b\) are in the same left coset of \(H\) in \(G\) if and only if \(aH=bH\) and, hence, \(ah_1=bh_2\) for some \(h_1, h_2 \in H\). Now,

\[\begin{align*} &ah_1 = bh_2\\ \iff &a= bh_2 h-1^{-1} \\ \iff &b^{-1}a =h_2h_1^{-1} \\ \iff &b^{-1}a \in H \end{align*}\]

The last step follows from the fact that if \(h_1, h_2 \in H\), then since \(H\) is itself a group it is closed under product and inverse and, hence, \(h_2h_1^{-1} \in H\). Then it follows that \(b^{-1}a \in H\) and, hence, we must have that for any two group elements \(x\) and \(y\), they are in the same coset if and only if \(y^{-1}x \in H\), for the given subgroup \(H\). (This is just a relabelling where \(x=a\) and \(y=b\)). So we can now define our relation that results in coset formation as follows: let \(H\) be a subgroup of a finite group \(G\) and let \(x, y \in G\), then \(xRy\) if and only if \(y^{-1}x \in H\). We now need to show that this is indeed an equivalence relation.

• Reflexive:

  \[x^{-1}x = e \in H \implies xRx \forall x \in G\]

• Symmetric:

  \[y^{-1}x \in H \iff (y^{-1}x)^{-1} \in H \iff x^{-1}y \in H \iff yRx\]

• Transitive:

  Suppose \(xRy\) and \(yRx\), then \(y^{-1}x \in H\) and \(z^{-1}y \in H\). This means that \((z^{-1}y)(y^{-1}x) \in H\). Therefore \(z^{-1}x \in H\) and \(xRz\).

We have established that left coset formation is an equivalence relation, so we now know that it must partition the group. We also know, from Abstract Algebra, that the size of every coset is equal to the size of \(H\) and, therefore, we can conclude that the size of \(H\) must divide the size of \(G\).

The above also gives us a checking lemma to determine whether two left cosets are equal. It uses the fact that two left cosets are either disjoint or identical and that \(g \in gH\).

Lemma 1.1 Let \(H\) be a subgroup of \(G\) and \(g_1, g_2 \in G\). Then \[g_1H = g_2H \ifif g_1^{-1}g_2 \in H.\]

Proof.

Suppose \(g_1H = g_2H\). Note that \(g_2 \in g_2 H\) since \(g_2 = g_2 e\) and \(e \in H\). Since \(g_1H = g_2 H\) there is an element \(h \in H\) such that \(g_1h = g_2\). Therefore \(h = g_1^{-1}g_2\) and so \(g_1^{-1}g_2 \in H\) as required.

On the other hand, suppose \(g_1^{-1}g_2 \in H\). Let \(h \in H\), then \[g_1h = eh= (g_2g_2^{-1})g_1h = g_2(g_2^{-1}g_{1})h = g_2((g_2^{-1}g_1)h) \in g_2 H\] since \(g_2^{-1}g_1 = (g_1^{-1}g_2)^{-1} \in H\). Similarly, \[g_2h = g_1(g_1^{-1}g_2)h \in g_1 H.\]

Since \(h \in H\) was chosen arbitrarily, we conclude that \(g_1H = g_2H\).

1.3 An Idea of What is to Come

Earlier we presented the Cayley tables of all the isomorphically distinct groups up to order 6, by which we mean that any group of order less than or equal to 6 is isomorphic to exactly one group in that list. The fundamental problem of Group Theory is to produce such a catalogue for all groups, or perhaps just all finite groups. Clearly it is not possible, nor particularly helpful, to produce an infinite list of Cayley tables, but for a given order \(n\) can we describe or generate all of the isomorphically distinct groups of that order? We know this is possible for all of the finite abelian groups, by way of the Fundamental Theorem of Finite Abelian Groups, so, it is the non-abelian groups that cause all the trouble in terms of trying to establish a classification. The most celebrated result in Group Theory is the classification of all finite simple groups. Simple groups will be defined later, but are the building blocks of all finite groups in much the same way that the primes are the building blocks of the positive integers. This classification theorem is the result of over 100 years’ work by thousands of group theorists and it is estimated that its complete proof (if ever assembled in one place) would require about 20,000 pages! In this module we will prove some classification and structure theorems, but we will also look at how groups arise naturally (albeit in some unexpected places). In doing so we shall be looking at the forms that different groups can take - in particular their actions, presentations and representations. The first unexpected place that group theory arises is in the bedroom….

1.4 Generators

1.4.1 The Mattress Problem

Good mattresses are expensive. Being a frugal individual I wish to maximise the amount of use that I get from my mattress so it is necessary to turn the mattress at regular intervals (say once a month) so as to promote uniform wear. Obviously any turning of the mattress must result in the mattress fitting back onto the bed as intended and, therefore, we can consider this problem in terms of the symmetries of a rectangle (assuming that the mattress is not square!) where the mattress represents the rectangle and the base of the bed represents the two-dimensional plane. Now, we know that the symmetry group of a rectangle is isomorphic to \(\Z_2 \times \Z_2\) (there are only two groups, up to isomorphism, of order 4 and the other is cyclic) and hence there are four positions for the mattress, or one per month for a four-month period. The symmetries are a rotation of \(180^{\circ}\) degrees, a ‘flip’ about the short axis, and a ‘flip’ about the long axis. Suppose we designate as \(A\) the \(180^{\circ}\) rotation (where the mattress remains face up), as \(B\) the ‘flip’ in the long axis of symmetry, and as \(C\) the ‘flip’ in the short axis of symmetry. What is the best sequence of moves for the mattress?

We could try each move in turn:

This is not a good solution since the initial configuration of the mattress is repeated at the end — a configuration is missing,

A better solution, which does not use \(C\), but gives even cover is: \(ABABABA\ldots\)

1.4.2 Finitely Generated Groups

In the Abstract Algebra module we found that the set of integer powers of an element of a group, \(G\), generates a cyclic subgroup of \(G\). If \(a\) is an element of \(G\), and has finite period \(k\) in \(G\), then this subgroup is \[\langle a \rangle = \{e, a, a^2, \ldots, a^{k-1}\}.\] Since this subgroup has order \(k\), the element \(a\) has order \(k\) (some authors write \(|a| = k\)). If there is an element \(a \in G\) such that \(\langle a \rangle = G\), then, as we know, \(G\) is a cyclic group and \(a\) is a generator of \(G\). Clearly \(\langle a \rangle\) is the smallest subgroup of \(G\) containing \(a\) in the sense that every subgroup of \(G\) which contains \(a\) must also contain \(\langle a \rangle\). We can generalise this to any subset of elements of \(G\).

We can generalise this to the following:

Definition 1.13 Let \(G\) be a group and let \(S = \{a_1, a_2, \ldots \}\) be a subset of the elements of \(G\). The subgroup generated by \(S\) is the smallest subgroup of \(G\) containing \(S\) (we denote this \(\langle S \rangle = \langle a_1, a_2, \ldots \rangle\). If this subgroup is all of \(G\) then \(S\) generates \(G\) and the \(a_i\) are generators of \(G\). If there is a finite set, \(S\), which generates \(G\), then \(G\) is finitely generated.

So, given a group \(G\) and a subset of elements \(S\), what does the subgroup generated by \(S\) look like? The following theorem answers this question.

Theorem 1.2 If \(G\) is a group and \(S = \{a_1, a_2, \ldots \}\) a subset of the elements of \(G\), then the subgroup \(\langle S \rangle\) of \(G\) consists of those elements of \(G\) that are finite products of integral powers of the \(a_i\) (where powers of a given \(a_i\) may occur several times in the product).

Proof.

First observe that a finite product of integral powers of elements of \(S\) must be contained in \(\langle S \rangle\) since \(S\) is contained in \(\langle S \rangle\). It therefore suffices to show that the set \(H\) of finite produces integral powers of elements of \(S\) is a subgroup of \(G\). This is because the set \(H\) would then be a subgroup of \(G\) containing \(S\) that is a subset of \(\langle S \rangle\), as \(\langle S \rangle\) is the smallest subgroup of \(G\) containing \(S\) it must therefore be equal to \(H\).

We check the subgroup criteria hold for \(H\).

1. For any \(a \in S\), \(a^0 = e \in H\), so \(H\) is non-empty and contains the identity of \(G\).
2. By definition \(H\) is closed under products.
3. \(H\) is closed under inverses since the inverse of a finite product of integral powers of elements of \(S\) is again a finite product of integral powers of elements of \(S\).

Example 1.6  

Consider \(D_4\). Note that \(D_4\) is not a cyclic group since it cannot be generated by a single element (the order of \(D_4\) is \(8\) and the order of an element of \(D_4\) is either \(2\) or \(4\)). However \(D_4\) can be generated using a proper subset of elements of \(D_4\).

\[\begin{array}{c|cccccccc} \circ&e&r_1&r_2&r_3&s_1&s_2&s_3&s_4\\ \hline e&e&r_1&r_2&r_3&s_1&s_2&s_3&s_4\\ r_1&r_1&r_2&r_3&e&s_4&s_1&s_2&s_3\\ r_2&r_2&r_3&e&r_1&s_3&s_4&s_1&s_2\\ r_3&r_3&e&r_1&r_2&s_2&s_3&s_4&s_1 \\ s_1&s_1&s_2&s_3&s_4&e&r_1&r_2&r_3 \\ s_2&s_2&s_3&s_4&s_1&r_3&e&r_1&r_2 \\ s_3&s_3&s_4&s_1&s_2&r_2&r_3&e&r_1 \\ s_4&s_4&s_1&s_2&s_3&r_1&r_2&r_3&e \end{array}\]

Let \(S = \{r_1,s_2\}\). Now the set of integral powers of \(r_1\) is precisely \(\{e,r_1, r_2, r_3\}\). To obtain the reflections \(s_1, s_3\) and \(s_4\) observe that

\[\begin{align*} r_1 s_2 &= s_1 \\ r_1 s_1 &= s_4 \\ r_1 s_4 &= s_3 \end{align*}\]

We conclude that \(\gen{r_1, s_2} = D_4\) and \(D_4\) is finitely generated.

1.5 Presentations

In essence, a group presentation is a notation that describes a group in terms of its generators and relations that hold between them. We begin with a definition.

Definition 1.14 (Presentation) A group can be described concisely by the notation \[\langle a, b \ldots \; | \; \text{list of relations between a, b, $\ldots$ , and their powers}\, \rangle,\] where the first part is a list of generators for the group and the second is a list of the relations that generate all the relations that hold between the generators. This notation is called a presentation of the group.

Example 1.7 Consider the presentation \[\langle a, b \; | \; a^2 = b^2 = 1, ab = ba \rangle.\]

The generators both have order \(2\) and commute. This means that any finite product integral powers of the generators \(a,b\) can be reduced, using the relations, to the form \(a^{i}b^{j}\) where \(i,j \in \{0,1\}\). Computing the operation table:

\[ \begin{array}{c|cccc} \ast & 1 & a & b & ab \\ \hline 1 & 1 & a & b & ab \\ a & a & 1 & ab & b \\ b & b & ab & 1 & a \\ ab & ab & b & a & 1 \end{array} \]

Observe that the group is abelian and is in fact isomorphic to \(\Z_2 \times \Z_2\).

Example 1.8 Consider the presentation \[\langle a, b \; | \; a^3 = b^2 = 1, ab = ba^{-1} \rangle.\]

The generator \(a\) has order \(3\) and so has inverse \(a^2\); the generator \(b\) has order \(2\) and is its own inverse. The relation \(ab=ba^{-1}\) means we can move \(b\) to the left of \(a\) at the cost of replacing \(a\) with its inverse. Consequently, by repeatedly moving \(b\)’s to the left of \(a\)’s any finite product of integral powers of \(a\) and \(b\) can be written in the from \(b^{i}a^{j}\) where \(i \in \{0,1\}\) and \(j \in \{0,1,2\}\).

We can compute the operation table. \[ \begin{array}{c|cccccc} \ast & 1 & a & a^2 & b & ba & ba^2 \\ \hline 1 & 1 & a & a^2 & b & ba & ba^2 \\ a & a & a^2 & 1 & ba^2 & b & ba \\ b & b & ba & ba^2 & 1 & a & a^2 \\ ba & ba & ba^2 & a^2 & 1 & a & b \\ ba^2 & ba^2 & b & ba & a & a^2 & 1 \end{array} \] Clearly this group is not abelian since \(ba \ne ab = ba^{2}\).

Looking at the above two presentations, we can see that the first is clearly abelian (because there are only two generators \(a\) and \(b\) and \(ab = ba\)), whereas the second is clearly non-abelian (because \(ab = ba^{-1}\) and \(a^{-1} \neq a\)). In each case it was also easy to determine the order of each group and write out the group elements in some form. In the next two examples this is not so obvious.

Example 1.9 \(\langle a, b \; | \; a^2 = b^2 = 1, (ab)^3 = 1 \rangle.\)

Notice that \(a\) and \(b\) both have order \(2\) in this case. Further observe that since \(ab ab ab = 1\) then \(bab = aba\). Thus \(baba = bbab=ab\) and \(abab= babb = ba\). Any finite product of integral powers of \(a\) and \(b\) can be written as a product of \(a\) and \(b\)’s. Moreover, such a product cannot have consecutive \(a\)’s or consecutive \(b\)’s. Using the observation \(baba =ab\) and \(abab = ba\) we notice that such a product cannot exceed length \(3\). This leaves products of the form \(a, ab,aba, b, ba\). The multiplication table is now
\[ \begin{array}{c|cccccc} \ast & 1 & a & b & ab & ba & aba \\ \hline 1 & 1 & a & b & ab & ba & aba \\ a & a & 1 & ab & b & ab & ba \\ b & b & ba & 1 & aba & a & ab \\ ba & ba & b & aba & 1 & ab & a \\ aba & aba & ab & ba & a & b & 1 \end{array} \] Note that is group is isomorphic to \(D_3\). The reflections are \(a,b\) and \(aba\) and the rotations are powers of \(ab\).

Example 1.10 \(\langle a, b \; | \; b^2a = b, ba^2b = a \rangle.\)

This group is the trivial group. From \(b^2 a = b\) we find that \(ba =1\). From \(ba^2b =a\) we find that \(ab = a\) and so \(b =a\). Using \(ba=1\) we see that \(a=1\) as well.

A good presentation provides an efficient description of a group. For example, the dihedral group of order \(2n\), which is isomorphic to the symmetry group of a regular \(n\)-sided polygon, can be defined by the presentation \[D_n = \langle a, b \; | \; a^n = b^2 = 1, ba = a^{-1}b \rangle.\] It is easy to see that any product must belong to the set \(\{1, a, a^2, \ldots, a^{n-1}, b, ab, a^2b, \ldots, a^{n-1}b\}\) and any product may be reduced to an element of this set by reducing powers of \(a\) modulo \(n\), powers of \(b\) modulo 2, and bringing the \(a\)’s to the left, replacing \(a\) with \(a^{-1}\) when it `hops over’ a \(b\).

Example 1.11  

For \(D_6\) we have \[\gen{a,b \mid a^6=b^2=1, ba = a^{-1}b}.\]

Given a product, for instance \(a^{11}b^3 a^2b^{-1}a^{-1}b^4a\), we can apply the relation to reduce it to the form \(a^{i}b^{j}\) for \(0 \le i \le 5\) and \(0 \le j < 2\).

\[\begin{align*} a^{11}b^3 a^2b^{-1}a^{-1}b^4a &= a^5 b a^2 b\\ &= a^5 a^{-2}b^2 \\ &= a^3 \end{align*}\]

1.6 Free Groups and the Word Problem

Informally the free group on a (possibly infinite) set of generators \(\{a, b, c, \ldots\}\) consists of all finite products involving integer powers of the generators where there are no relations to tell us how to reduce products, with the obvious exception that, for example, \(ab^2b^{-3}a=ab^{-1}a\) etc. The products formed in this way are called words. Fundamentally, all groups can be thought of as consisting of infinitely many words but, using relations, we may be able to reduce each of these to a member of a (possibly finite) set. As we have seen, things are not always this easy. For a given presentation it can be difficult to determine the order of the group or even whether it is finite or infinite. This is summed up by the so called Word Problem for groups. The Word Problem is to find an algorithm which will determine whether two words represent the same element. We have such an algorithm for the dihedral group \(D_n\) because we have a way of reducing any given word to one of the \(2n\) elements of \(\{1, a, a^2, \ldots, a^{n-1}, b, ab, a^2b,\ldots, a^{n-1}b\}\). Hence two words are equal if and only if they reduce to the same element. It is hard to imagine that this would not be the case for any group presentation, but remarkably the Word Problem is known to be unsolvable in general.

1.7 Revision Sheet

This is a revision sheet and covers material from Abstract Algebra.

---

Question R.1

Define \(*\) on \(\rwz\) by \(a*b=|a| \, b\) (so, for example \(2*3=6, -2*3=6, 2*(-3)=-6\) etc.).

1. Show that \(*\) is an associative binary operation on \(\rwz\).
2. Show that there is an element \(e \in \rwz\) such that \(e*x = x, \; \forall \, x\in \rwz\).
3. Show that \(\forall \, x\in \rwz, \, \exists \, x^{-1}\in\rwz\) such that \(x*x^{-1}=e\).
4. Is \((\rwz,*)\) a group?

Solution R.1

1. We have that, for all \(x, y, z \in \rwz\), \[(x*y)*z = (|\, x \, | \, y)*z = |\, |\, x \, | \, y\, | z = |\, xy \, | z\] and \[x*(y*z) = x* (|\, y \, | \, z) = | \, x \, | (|\, y \, | \, z) = |\, xy \, | z.\] Hence \(*\) is associative on \(\rwz\).

2. For all \(x \in \rwz\) we have that \(1*x = | \, 1 \, |x = x\), so \(e = 1\). Note also, however, that \(e = -1\) also works.

3. Note that \(x * \D\frac{1}{| \, x \, |} = | \, x \, | \frac{1}{| \, x \, |} = 1\), so \(x^{-1} = \D\frac{1}{| \, x \, |}\).

4. No, it is not. There are a number of ways of deciding this.

   1. In part ii. we noted that there were two values of \(e\) that would satisfy the relationship \(e*x=x\) for all \(x \in \rwz\), namely \(1\) and \(-1\). So both of these appear to have the property of an identity, but we know that in any group the identity is unique.
   2. We also know that the identity in a group must commute with every element of the group, that is it must be `two-sided’ in the sense that it must satisfy \(e*x = x*e = x\). This is not the case here; for example, try \(x = -3\) (with \(e=1\) or \(-1\)) and note that \(e*x \neq x*e\).
   3. Similarly, we can also see that the ‘inverse’ found in part iii. is not ‘two-sided’.

Question R.2

If \(H\) is a subgroup of a finite group \(G\) then the right coset of \(H\) by \(g\) is denoted and defined by \[Hg=\{hg \, | \, h\in H\}.\] Prove Lagrange’s Theorem using right cosets (the proof using left cosets was given in the second year Abstract Algebra module). In other words, show that every right coset, \(Hg\), of \(H\) is the same size as \(H\), that two right cosets of \(H\) are either disjoint or equal, and that every element of \(G\) is in a right coset of \(H\). Finally deduce that the order of \(H\) divides the order of \(G\).

Solution R.2

Since \(H\) is finite (say with order \(m\)) we may write \(Hg=\{h_1g, h_2g,\ldots, h_mg\}\). It looks as if this set has size \(m\) (as it contains \(m\) symbols) but remember that \(\{1,1,2\}\) is a set of size 2 not 3. So to show that \(Hg\) really does have size \(m\) we need to show that all the symbols represent distinct group elements. As is often the case with pure mathematics, once we have worked out what we need to do actually doing it is straightforward. \[h_ig=h_jg\imp h_i=h_j \;\text{(by cancellation) so }|Hg|=m=|H|.\] To prove that two right cosets are either identical or disjoint we show that if they have an element in common then they are identical. Suppose \(Hg_1\cap Hg_2\neq\emptyset\) and let \(x\in Hg_1\cap Hg_2\). Then \(\exists \, h_1,h_2\in H\) such that \(h_1g_1=x\) and \(h_2g_2=x\). It follows that \(g_1=h_1^{-1}h_2g_2\) (we will use this later). Let \(z\) be any element of \(Hg_1\). We will show that \(z\in Hg_2\), from which it will follow that \(Hg_1\subseteq Hg_2\). Let’s pause to think how we can do this - the fact that \(z\in Hg_1\) means that \(z\) can be written as an element of \(H\) times \(g_1\). To show that \(z\in Hg_2\) we need to write \(z\) as an element of \(H\) times \(g_2\). We will use the facts that \(g_1=h_1^{-1}h_2g_2\) and that \(H\) is a subgroup so any product of elements of \(H\) is another element of \(H\). Here goes… \(z\in Hg_1\), so \(\exists h\in H\) such that \(z=hg_1\). But \(g_1=h_1^{-1}h_2g_2\), so \(z=(hh_1^{-1}h_2)g_2\in Hg_2\), because \(hh_1^{-1}h_2\in H\). So \(Hg_1\subseteq Hg_2\) and a similar argument shows that \(Hg_2\subseteq Hg_1\). It follows that \(Hg_1=Hg_2\) as required. Finally we show that every element is in a right coset. This is the easiest part of all because \(H\) contains the identity element \(e\in G\) so \(\forall \, g\in G,\ eg=g\) and hence \(g\in Hg\). Putting these facts together we have that the right cosets of \(H\) partition the elements of \(G\) into disjoint subsets which are all the same size as \(H\). It follows that the number of elements in \(G\) must be a multiple of the number of elements in \(H\) (where this multiple is the number of right cosets). In other words the order of any subgroup must divide the order of the group (Lagrange’s Theorem).

Question R.3

Let \(G\) be a group and \(H\) the subset of \(G\) consisting of the identity \(e\) and all elements of \(G\) of order 2, so \(H=\{h\in G| h^2=e\}\). Show that:

1. if \(G\) is abelian, then \(H\) is a subgroup of \(G\),
2. if \(G\) is non-abelian, then \(H\) is not necessarily a subgroup of \(G\).

Solution R.3

Here we are being asked to prove that something is true for abelian groups but false for non-abelian ones. The first thing to do is make sure we know what the statement is! Let’s look at \(G=\Z_4\), we have \(0+0=0, 1+1=2, 2+2=0\) and \(3+3=2\), so \(H=\{0,2\}\) and sure enough this forms a subgroup of \(\Z_4\). Now let’s look at \(D_3\), using the Cayley table for \(D_3\) in the list of Cayley tables just after Example 1.2 we have \(H=\{0,3,4,5\}\). This is clearly not a subgroup of \(D_3\), for one thing \(4\) does not divide \(6\) (which would upset Lagrange) or, if you prefer, \(3*4=1\) so \(H\) is not closed. It’s important to use examples in this way even though we cannot use examples to prove statement i.; they are important in helping us understand what the statement means. Notice that we have answered part ii.! For this we only require a single counter-example and we’ve found one in \(D_3\).

Let’s try to prove i.. We need one of our subgroup checking lemmas. Because we are not told that \(G\) is finite we need to use Lemma 2.6 from the Abstract Algebra module. Firstly, since \(e^2=e\) we have \(e\in H\) so \(H\) is non-empty. We now need to show that \(H\) is closed, that is if \(h_1,h_2\in H\) then \(h_1*h_2\in H\). If \(h_1,h_2\in H\), then \(h_1^2=h_2^2=e\) (and we need to show that \((h_1h_2)^2=e\)). Once we know what we are trying to show, and what we must use, we can write this concisely as follows. \(h_1,h_2\in H\ \imp (h_1h_2)^2=h_1h_2h_1h_2=h_1^2h_2^2=e*e=e\) so \(h_1h_2\in H\) as required. If \(H\) were finite then we would be done but because \(H\) may be infinite we need to show that the inverse of every element in \(H\) is also in \(H\). This is easy once we notice that \(h^2=e\imp h^{-1}=h\). So the inverse of every element in \(H\) is also in \(H\)!

Question R.4

Show that if \(H\) and \(K\) are subgroups of an abelian group \(G\), then \[HK = \{ hk \, | \, h \in H, k \in K \}\] is a subgroup of \(G\). Is this true for non-abelian groups?

Solution R.4

Again, we do not know whether \(HK\) is a finite or infinite set, so we need to prove closure and then show that every element in the set also has its inverse in the set. In addition, it is obvious that both \(H\) and\(K\), and hence \(HK\), are non-empty. As usual, to prove closure we take two ‘typical’ elements of our subset and demonstrate that when they are combined under the binary operation of the group the resulting product remains in the subset. In order to do this it is important to know how membership of the subset is defined. Here we know that every element of \(HK\) is of the form \(hk\), where \(h \in H\) and \(k \in K\). It therefore follows that if \(a \in HK\) there must be an \(h \in H\) and a \(k \in K\) such that \(a = hk\). Note, also, that as the group is abelian \(hk = kh\). We then proceed as follows:

Let \(a, b \in HK\), so \(\exists \, h_1, h_2 \in H\) and \(\exists \, k_1, k_2 \in K\) such that \(a = h_1k_1\) and \(b = h_2k_2\). Then, \[ab = h_1k_1h_2k_2 = h_1h_2k_1k_2 \in HK\] since \[h_1h_2 \in H, k_1k_2 \in K.\] Note that the second step is valid since the group is abelian and the final step is valid since \(H\) and \(K\) are both groups so must be closed. To show that the subset \(HK\) is closed under inverses we need to remember an important property of inverses, namely that \((xy)^{-1} = y^{-1}x^{-1}\). Now, \[a^{-1} = (h_1k_1)^{-1} = k_1^{-1}h_1^{-1} = h_1^{-1}k_1^{-1} \in HK\] since \[h^{-1} \in H, k^{-1} \in K.\] Note, again, that the second step is valid since the group is abelian and the final step is valid since \(H\) and \(K\) are both groups so must be closed under inverses. This statement is not true for non-abelian groups. For example \(H = \{e, s_1\}\) and \(K = \{e, s_2\}\) are subgroups of \(D_3\), but \(HK = \{e, s_1, s_2, r_1\}\) is not a subgroup of \(D_3\).

Question R.5

Let \((G_1, \times)\) and \((G_2, \circ)\) be groups and \(\theta \, : \, G_1 \rightarrow G_2\) an isomorphism. Prove that \(H\) is a subgroup of \(G_1\) if and only if \(\theta (H) = \{\theta(h) \, | \, h \in H \}\) is a subgroup of \(G_2\).

Solution R.5

The usual procedures and caveats for proving ‘subgroupness’ apply here. It is also important to note that different binary operations are at work, depending on the group, and that this is an ‘if and only if’ statement so both forward and backward implications need to be considered. It should also be obvious that we will need to use the definition of an isomorphism, that is a bijective mapping from \(G_1\) to \(G_2\) such that for all \(a, b \in G_1\), \(\theta(a \times b) = \theta(a) \circ \theta(b)\). Taking the forward implication first, the proof then proceeds as follows (bearing in mind that we are trying to show that \(\theta (H)\) is a subgroup of \(G_2\)):

Let \(H\) be a subgroup of \(G_1\). Clearly both \(H\) and \(\theta(H)\) are non-empty. Let \(h_1^{\prime}, h_2^{\prime}\) be any two elements of \(\theta H\). Then \(\exists \, h_1, h_2 \in H\) such that \(\theta (h_1) = h_1^{\prime}\) and \(\theta (h_2) = h_2^{\prime}\). Hence \[h_1^{\prime} \circ h_2^{\prime} = \theta (h_1) \circ \theta (h_2) = \theta (h_1 \times h_2) \in \theta(H)\] since \[h_1 \times h_2 \in H.\] The second step above uses the definition of an isomorphism and the last step is justified since we know that \(H\) is a group and therefore closed.

Now, for all \(h^{\prime} \in \theta(H)\) there exists \(h \in H\) such that \(\theta (h) = h^{\prime}\). But \[(h^{\prime})^{-1} = (\theta (h))^{-1} = \theta(h^{-1}) \in \theta(H)\] since \[h^{-1} \in H.\]

For the backward implication (converse), that is if \(\theta(H)\) is a subgroup of \(G_2\) then \(H\) is a subgroup of \(G_1\), we either construct a similar argument to that above or (much better) use the fact that \(\theta^{-1} : G_2 \rightarrow G_1\) is an isomorphism from \(G_2\) to \(G_1\) and so the result follows immediately.

Question R.6

Show that if \(G\) is an abelian group then \[\{ g^2 \, | \, g \in G \}\] is a subgroup of \(G\), but this is not true for groups in general.

Solution R.6

You should be used to the process by now! Let \(H = \{ g^2 \, | \, g \in G \}\). Clearly \(H\) is non-empty by definition. Let \(a, b \in H\). Then there exist \(g_1, g_2 \in G\) such that \(a = g_1^2\) and \(b = g_2^2\). Then, \[ab = g_1^2g_2^2 = g_1g_1g_2g_2 = g_1g_2g_1g_2 = (g_1g_2)^2 \in H\] since \[g_1g_2 \in G.\] Further, \[a^{-1} = (g_1^2)^{-1} = g_1^{-2} = (g_1^{-1})^2 \in H\] since \[g_1^{-1} \in G.\] Hence, \(H = \{ g^2 \, | \, g \in G \}\) is a subgroup of G.

To show that this is not the case for groups in general we need to find a non-abelian group to give us a counter example, but this isn’t obvious. We would usually look to the dihedral groups to provide such a counter example, but, in fact, the given statement is true for \(D_n\) for all \(n\). (Can you see why? If not, ask!). In fact we need to go to \(A_4\), a group of order 12, to find the first counter example. Why this group provides a counter example will become clearer once we have completed the chapter on permutations, but the reason is as follows. \(A_4\) consists of the identity, 8 permutations of the form \((* \; * \; *)\) and 3 permutations of the form \((* \; *)(* \; *)\) (12 elements in total). Since squaring the identity or the permutations of the form \((* \; *)(* \; *)\) gives the identity and squaring the 3-cycles just gives the 3-cycles (all eight of them), then the subset \(H = \{ g^2 \, | \, g \in A_4 \}\) contains nine elements. This cannot form a subgroup of \(A_4\) as that would violate Lagrange’s Theorem.

Question R.7

We know that every proper subgroup of a cyclic group is itself cyclic. State the converse and give a counter example to demonstrate that the converse is false.

Solution R.7

The converse of the statement is “If a group \(G\) is such that every proper subgroup is cyclic, then \(G\) is cyclic”. This statement is false since any non-cyclic group of order \(pq\) where \(p\) and \(q\) are prime (e.g \(D_{pq}\)) has only proper subgroups of prime order which are necessarily cyclic (as is \(\{e \}\)).

Question R.8

In each of the following cases, find the order of the given element in the direct product:

1. \((3, 7)\) in \(\Z_9 \times \Z_{14}\);
2. \((8, 11)\) in \(\Z_{10} \times \Z_{15}\);
3. \((3, 7, 12)\) in \(\Z_4 \times \Z_{10} \times \Z_{15}\).

Solution R.8

First, recall that to find the order of \((a, b)\) in \(G_1 \times G_2\), where \(a \in G_1\) and \(b \in G_2\), we take the lowest common multiple of the orders of \(a\) in \(G_1\) and \(b\) in \(G_2\). Remember, also, that an element \(a\) in \(\Z_m\) has order equal to \(m/\gcd(a, m)\).

1. \((3, 7)\) in \(\Z_9 \times \Z_{14}\). Obviously 3 has order 3 in \(\Z_9\) and 7 has order 2 in \(\Z_{14}\). So the order of \((3, 7)\) in \(\Z_9 \times \Z_{14}\) is lcm\((3, 2) = 6\).
2. \((8, 11)\) in \(\Z_{10} \times \Z_{15}\): The order of 8 in \(\Z_{10}\) is 10/gcd\((8, 10) = 5\). Similarly the order of 11 in \(\Z_{15} = 15\). So, the order of \((8, 11)\) in \(\Z_{10} \times \Z_{15}\) is lcm\((5, 15) = 15\).
3. \((3, 7, 12)\) in \(\Z_4 \times \Z_{10} \times \Z_{15}\). The order of 3 in \(\Z_4\) is 4/gcd(3, 4) = 4. Similarly the order of 7 in \(\Z_{10} = 10\), and the order of 12 in \(\Z_{15} = 5\). So, the order of \((3, 7, 12)\) in \(\Z_4 \times \Z_{10} \times \Z_{15}\) is lcm\((4, 10, 5) = 20\).

Question R.9

1. Write down all of the generators of
   1. \(\Z_{14}\),
   2. \(\Z_{15}\).
2. Classify, according to the Fundamental Theorem of Finite Abelian Groups, all of the abelian groups of orders
   1. 54,
3. In part ii.a. above, state which of the groups of order 54 is cyclic and which is isomorphic to \(\Z_6 \times \Z_9\).

Solution R.9

1. Recall that the generators of \(\Z_m\) are those elements that are relatively prime to \(m\). So the generators of \(\Z_{14}\) are 1, 3, 5, 9, 11, 13 and the generators of \(\Z_{15}\) are 1, 2, 4, 7, 8, 11, 13, 14.
2. We state, first, the Theorem: >Every finitely abelian group is isomorphic to a direct product of cyclic groups of the form \[\Z_{p_1^{r_1}}\times\Z_{p_2^{r_2}}\times \cdots \times \Z_{p_n^{r_n}}\] where the \(p_i\) are primes, not necessarily distinct (and \(r\) may be 0).
   1. Now, \(54 = 2 \times 3 \times 3 \times 3\), which is its prime decomposition. Hence the possible groups, in accordance with the theorem, are \(\Z_2 \times \Z_{27}\), \(\Z_2 \times \Z_3 \times \Z_9\), and \(\Z_2 \times \Z_3 \times \Z_3 \times \Z_3\).
   2. \(600 = 2^3 \times 3 \times 5^2\). So the isomorphically distinct groups are \(\Z_8 \times \Z_3 \times \Z_{25}\), \(\Z_2 \times \Z_4 \times \Z_3 \times \Z_{25}\), \(\Z_2 \times \Z_2 \times \Z_2 \times \Z_3 \times \Z_{25}\), \(\Z_8 \times \Z_3 \times \Z_5 \times \Z_5\), \(\Z_2 \times \Z_4 \times \Z_3 \times \Z_5 \times \Z_5\), and \(\Z_2 \times \Z_2 \times \Z_2 \times \Z_3 \times \Z_5 \times \Z_5\).
3. Remember that \(\Z_r\) is isomorphic to \(\Z_m \times \Z_n\) if and only if \(r = mn\) and \(m\) and \(n\) are relatively prime. So, for example, \(\Z_{12}\) is not isomorphic to \(\Z_6 \times \Z_2\) as 6 and 2 are not relatively prime. If we are dealing with a direct product of more than two cyclic groups then the same principle applies except that the orders have to be pairwise relatively prime. Now we know that \(\Z_n\) is cyclic for all \(n\), so \(\Z_{54}\) must be cyclic. This is isomorphic to \(\Z_2 \times \Z_{27}\) since 2 and 27 are relatively prime, so \(\Z_2 \times \Z_{27}\) must be cyclic. The group that is isomorphic to \(\Z_6 \times \Z_9\) is \(\Z_2 \times \Z_3 \times \Z_9\), since \(\Z_2 \times \Z_3 \cong \Z_6\) as 2 and 3 are relatively prime.

1.8 Problem Sheet 1

For the example class in Week 3; covers Chapter 1 material. At minimum you should attempt questions 1.4, 1.5 and 1.7.

---

Question 1.1

Let \(R\) be a relation on a non-empty set, \(S\)

1. Define a relation on \(\Z^+\) by, for \(x, y \in \Z^+\), \(xRy\) if and only if \(x\) and \(y\) have the same number of digits in the usual base 10 notation. Show that this is an equivalence relation.
2. Find the equivalence class containing \(37\).

Solution 1.1

Recall that, for a relation to be an equivalence relation, we require that it is reflexive, symmetric and transitive. These terms are defined as follows: A relation, \(R\), on a non-empty set \(S\) is said to be

1. reflexive: if \(aRa\) for all \(a \in S\),
2. symmetric: if, whenever \(aRb\), then \(bRa\),
3. transitive if, whenever \(aRb\) and \(bRc\), then \(aRc\).

Applying the definitions to our relation:

1. trivial, since an integer has the same number of digits as itself so \(xRx\);
2. again, it is obvious that if \(x\) has the same number of digits as \(y\) then \(y\) has the same number of digits as \(x\), so if \(xRy\) then \(yRx\);
3. it is clear that if \(w \in \Z^+\) and \(xRw\) and \(wRy\), then \(xRy\).

Thus \(R\) is an equivalence relation on the set \(S\). Obviously, all of the members of any given equivalence class must have the same number of digits. thus the class containing 37 will be \([37] = \{10, 11, \; \ldots, 37, \ldots \; , 99 \}\).

Question 1.2

Define a relation on \(\R\) by, for \(a, b \in \R\), \(aRb\) if and only if \(| \, a \, | = | \, b \, |\). Is this an equivalence relation? If so, how does it partition the set?

Solution 1.2

Applying the definitions to our relation:

1. \(a R a\) since, \(\forall a \in \R, \; |a| = |a|\).
2. If \(a R b\) then, by definition, \(|a| = |b|\). It then follows, since \(|b| = |a|\), that \(b R a\).
3. We know, for any real numbers \(x, y, z\) that if \(x = y\) and \(y = z\), then \(x=z\). Now, if \(a R b\) and \(b R c\) then \(|a| = |b|\) and \(|b| = |c|\) and hence it follows that \(|a| = |c|\) and so \(a R c\).

Thus \(R\) is an equivalence relation on the real numbers. The relation partitions \(\R\) as follows: \[[0] = \{ 0 \} \qquad \qquad [a] = \{ a, -a \} \quad \forall a \in \R.\]

Question 1.3

Define a relation that partitions the plane into the origin and all circles centred at the origin with radius \(r \in \R\). Prove that this is an equivalence relation.

Solution 1.3

Recall that a circle centred at the origin is the set of all points of the plane that are at a given distance from the origin. In Cartesian coordinates, a point \((x_1, y_1)\) has distance \(\sqrt{x_1^2 + y_1^2}\) from the origin. It follows that if a point \((x_2, y_2)\) lies on the same circle then \(\sqrt{x_1^2 + y_1^2} = \sqrt{x_2^2 + y_2^2}.\) Since distances are always positive we thus have that \(x_1^2 + y_1^2 = x_2^2 + y_2^2\). This allows us to define the relation that partitions the plane as described: \[(x_1, y_1) R (x_2, y_2) \quad \Leftrightarrow \quad x_1^2 + y_1^2 = x_2^2 + y_2^2.\] We now need to show that this is an equivalence relation.

1. Clearly \(x_1^2 + y_1^2 = x_1^2 + y_1^2\), hence \((x_1, y_1) R (x_1, y_1)\) and so the relation is reflexive.
2. Equally clearly, if \(x_1^2 + y_1^2 = x_2^2 + y_2^2\) then \(x_2^2 + y_2^2 = x_1^2 + y_1^2\), hence if \((x_1, y_1) R (x_2, y_2)\), then \((x_2, y_2) R (x_1, y_1)\), so the relation is symmetric.
3. If \((x_1, y_1) R (x_2, y_2)\) and \((x_2, y_2) R (x_3, y_3)\) then it follows that \(x_1^2 + y_1^2 = x_2^2 + y_2^2\) and \(x_2^2 + y_2^2 = x_3^2 + y_3^2\). Hence, \(x_1^2 + y_1^2 = x_3^2 + y_3^2\) and so \((x_1, y_1) R (x_3, y_3)\), demonstrating that the relation is transitive.

Thus we have demonstrated that the relation, as defined, is an equivalence relation.

Question 1.4

In the group \[\langle A, B, C\, |\, A^7=B^3=C^2=1, BA=A^3B, CA=AC, CB=B^2C\rangle\] express each of the following in the form \(A^rB^sC^t\):

1. \((BC)^2\);
2. \(B^2A^3\);
3. \(C^3B^{-2}\);
4. \((AB)^3\);
5. \((ABC)^{-1}\).

Solution 1.4

1. Here we use the fourth condition, namely \(CB = B^2C\), so \[(BC)^2 = BCBC = B(CB)C = B(B^2C)C = B^3C^2.\]

2. First, we repeatedly apply the second condition, \(BA = A^3B\), that is \[\begin{align*} B^2A^3 &= B(BA)AA = B(A^3B)AA = BA^3(BA)A\\ &= BA^3(A^3B)A = BA^6(BA) = BA^9B \end{align*}\] and then we use \(A^7 = 1\) so \[BA^9B = BA^2B = (BA)AB = A^3(BA)B = A^3(A^3B)B = A^6B^2.\]

3. First use the fact that \(C^2 = 1\), so \(C^3B^{-2} = CB^{-2}\). Now, \(B^3 = 1\), so \(BB^2 = 1\) and hence \(B^2 = B^{-1}\) or \(B^{-2} = B\). Then, \[C^3B^{-2} = CB^{-2} = CB = B^2C.\]

4. \((AB)^3 = ABABAB = A(BA)(BA)B\). We now use \(BA = A^3B\) on each of the bracketed expressions, \[A(BA)(BA)B = A(A^3B)(A^3B)B = A^4BA^3B^2.\] Now we use the same relation three times to ‘hop’ the \(A\) over the \(B\) as follows \[A^4BA^3B^2 = A^4(BA^3)B^2 = A^4(A^9B)B^2 = A^{13}B^3 = A^6\] as \(A^7 = 1\) and \(B^3 = 1\).

5. Note that \(A^7 = 1 \imp A^6 = A^{-1}\); \(B^3 = 1 \imp B^2 = B^{-1}\); \(C^2 = 1 \imp C = C^{-1}\). So \((ABC)^{-1} = C^{-1}B^{-1}A^{-1} = CB^2A^6\). Now use the relation \(CB = B^2C\) twice to ‘hop’ the \(B\) over to the front of the \(C\), that is \(CB^2A^6 = B^4CA^6 = BCA^6\) since \(B^3 = 1\). Next use \(CA = AC\) six times to ‘hop’ the \(A\) over the \(C\), \[BCA^6 = BA^6C.\] Finally we use \(BA = A^3B\) six times to ‘hop’ the \(A\) over the \(B\), that is \[BA^6C = A^{18}BC = A^4BC\] since \(A^7 = 1.\) And so we have that \((ABC)^{-1} = A^4BC\). You may, however, have approached this problem from a different angle. Suppose we start by ‘hopping’ the \(A\) over the \(B\). We can do this in two steps using \(BA = A^3B\) as follows: \[CB^2A^6 = CBBA^6 = CBA^{18}B = CBA^4B\] as \(A^7 = 1\). We now repeat that step four more times \[CBA^4B = CA^{12}BB = CA^5B^2\] since \(A^7 = 1\). Now apply \(CA = AC\) five times to ‘hop’ the \(A\) over the \(C\) as follows \(CA^5B^2 = A^5CB^2\). Finally, we use \(CB = B^2C\) to obtain \[A^5CB^2= A^5B^4C = A^5BC\] since \(B^3 = 1\). And so we have that \((ABC)^{-1} = A^5BC\). What has gone wrong? Well, actually, nothing at all has gone wrong! Both answers are perfectly valid. So what is going on?

Question 1.5

Let \(G = \langle a, b, c \, | \, a^4 = b^3 = 1, ab = ba, ac = ca, bc = cb \rangle\). Classify \(G\) according to the Fundamental Theorem.

Solution 1.5

Note that the generators commute with each other pairwise, so we know that the group is abelian. So every product can be reduced to the form \(a^ib^jc^k\) where \(0 \leq i < 4\), \(0 \leq j < 3\) and \(k \in \Z\) (no constraint on \(k\)). Hence, the group is isomorphic to \(\Z_4 \times \Z_3 \times \Z\) with the isomorphism given by \(a^ib^jc^k \mapsto (i, j, k)\).

Question 1.6

If \(G=\langle a,b\, | \, ab=ba, a^4=b^3=1 \rangle\) and \(H\) is the cyclic subgroup generated by \(b\), classify \(G\) according to the Fundamental Theorem, and find the left and right cosets of \(H\) in \(G\).

Solution 1.6

It should be obvious that \(G \cong \Z_4 \times \Z_3\). Note that this group is abelian and so the distinct right and left cosets will coincide. We have: \[\begin{align*} H &= \{0, b, 2b\}\\ a+H &= H+a = \{a, a+b, a+2b\}\\ 2a+H &= H+2a = \{2a, 2a+b, 2a+2b\}\\ 3a+H &= H+3a = \{3a, 3a+b, 3a+2b\}. \end{align*}\]

Question 1.7

In the dihedral group \(D_5=\langle a, b\, | \, a^5=1, b^2=1, ab=ba^{-1} \rangle\), simplify:

1. \(a^7b^3a^{-2}baba^3ba^2a^7b^2a\);
2. \(a^{13}b^5a^2b^{-7}a^2ba\).

Solution 1.7

1. First, using \(a^5 = 1\) and \(b^2 = 1\) we have \[a^7b^3a^{-2}baba^3ba^2a^7b^2a = a^2ba^3baba^3ba^4b^2a.\] Now bracket together all the terms \(ba\) and then use \(ab = ba^{-1} \imp ba = aba^2\). Hence \[\begin{align*} &a^2ba^3baba^3ba^4b^2a\\ &= a^2(ba)a^2(ba)(ba)a^2(ba)a^3b^2a\\ &= a^2(aba^2)a^2(aba^2)(aba^2)a^2(aba^2)a^4\\ &= a^3ba^5ba^3ba^5ba^6\\ &= a^3b^2a^3b^2a\\ &= a^7\\ &= a^2. \end{align*}\]
2. Note that, \(a^5 = 1\) and as \(b^2 = 1\), then \(b=b^{-1}\) and so \(b^n = b^{-n}\). Then \[\begin{align*} &a^{13}b^5a^2b^{-7}a^2ba\\ &= a^3ba^2ba^2ba\\ &= a^2(ab)a(ab)a(ab)a\\ &= a^2(ba^{-1})a(ba^{-1})a(ba^{-1})a\\ &= a^2bbb\\ &= a^2b. \end{align*}\]

Question 1.8

In \((\Q,+)\), describe the elements of \(\langle \frac{1}{2} \rangle\) and \(\langle \frac{1}{2},\frac{1}{3} \rangle\). Show that \((\Q,+)\) is not finitely generated.

Solution 1.8

In \((\Q,+)\), \(\langle \frac{1}{2} \rangle\) consists of all integer multiples of \(\frac{1}{2}\), so \(\langle \frac{1}{2} \rangle=\{\frac{n}{2} \, | \, n\in\Z\}\). For \(\langle \frac{1}{2},\frac{1}{3} \rangle\) we now have two generators, so the subgroup consists of all sums of multiples of \(\frac{1}{2}\) and \(\frac{1}{3}\). Hence \(\langle \frac{1}{2},\frac{1}{3} \rangle=\{\frac{m}{2}+\frac{n}{3} \, | \, m,n\in\Z\}=\{\frac{n}{6} \, | \, n\in\Z\}\). The final equality follows because gcd(2,3)=1 and hence every integer can be expressed in the form \(3m+2n\) (why?). Given a finite set \(S\) in \((\Q,+)\), \(\langle S \rangle\) will only contain rationals which can be expressed with denominator equal to the lowest common multiple of the denominators of the elements of \(S\). So any fraction whose denominator is not of this form is not in \(\langle S \rangle\) and hence \(\Q\) has no finite generating set. For an explicit example take a prime \(p\) greater than all the denominators in \(S\), then \(\frac{1}{p}\notin \langle S \rangle\).